1. Field of the Invention
This invention relates to sorting in general and more particularly to the sorting of qualified records that are contained in multiple record blocks of a segmented storage device.
2. Description of the Prior Art
Text processing systems providing automatically printed letters or other documents including fixed text that is used in each document merged with variable text to individualize the document are well known in the art. This function was performed by the dual tape IBM Magnetic Tape "Selectric".RTM. Typewriter by placing the fixed text on one tape and records of variable text on the other tape with switch codes appropriatedly interspersed in the text of the two tapes to cause merging of the text to provide printing of a series of individualized documents in a relatively unattended manner. This function was also provided in an improved manner in the IBM Mag Card II Typewriter, as described in the above-referenced, copending patent application Ser. No. 595,840. The flexibility of this function was further improved upon in the IBM 46/40 Document Printer, as described in the above-referenced, copending patent application Ser. No. 693,818, by provision of the capability to choose only selected fields of a record of variable data to be used exclusively in a letter while other fields are used for a corresponding envelope.
In none of the above systems is there a capability for the screening of records to provide automatically printed documents corresponding to only those records that quality in accordance with data supplied by an operator. For example, a field may be included with each record in a file that corresponds to the profession of the person named in the file. It may be desirable, for instance, to send a letter only to the dentists named in the file of records. Further, none of the above systems provided the capability to sort the records to, therefore, output the documents in a preferred order, such as alphabetically or grouped by postal zip code. Grouping of letters by zip code for mailing provides a discount in postal rates that becomes very significant in large mailings.
The qualifying and sorting of data has been long practiced in the art. For example, U.S. Pat. No. 3,343,133 entitled "Data Handling System" provides a background for the sorting of data. In discussing the object of providing documents in a sorted sequence from records that qualify in accordance with predetermined conditions, it becomes pertinent to consider the constraints and limitations of a practical office system to accomplish this result. Typically, a segmented storage device such as a disc or a magnetic tape, containing a plurality of fixed-length blocks, might be used to store a large file of records. Numerous records may be included on each block of the storage device. If unlimited random access memory is available, a relatively simple implementation is to read the entire file into the random access memory, rearrange the file in the memory by sorting and qualifying the records, and merging the appropriate fields of the records from the random access memory for output printing. With large files, this approach becomes economically prohibitive for a typical office text processing system.
In the referenced U.S. Pat. No. 3,343,133, the amount of random access memory needed to perform sorting is reduced by providing a plurality of segmented storage devices and means to transfer data from these devices back and forth through the memory. This approach, however, introduces a possibility of degradation of the integrity of the data in the files since errors may occur in writing the data back onto the storage devices. Alteration of the data on the storage devices also requires increased accessing of the blocks on the storage device which increases mechanical wear in the accessing mechanism, itself, and adds additional time to the sorting operation.
A technique known in the prior art as the quadratic sort has been used to order the sequence of data records by structuring these records into N record groups with each of the N record groups containing N records. Each of the groups are then sorted for the lowest or highest record in the group and then each of the sorted records are further sorted to find the lowest or highest record in the file. To apply this technique to a file having a variable number of records on a variable number of storage blocks, the data would have to be restructured on the storage device by reading it into a memory, dividing it into the same number of storage blocks as the square root of the number of records in the file and rerecording the data onto this number of storage blocks. However, the required number of storage blocks may not be available on the storage device. Further, as in the above technique, this technique introduces the possibility of alteration of the records due to writing errors and also increases the wear of the mechanical accessing components associated with the storage devices by the additional accessing required for rewriting the data.
It would therefore, be advantageous, to provide a system for sorting qualified data records to provide ordered, sequential accessing of appropriate records to a printing system in an economical and efficient manner, without introducing the possibility of alteration of the records due to writing errors and with minimization of wear of the mechanical accessing components associated with the storage device and with a substantially small random access memory requirement.